package com.leetcode;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 1326. 灌溉花园的最少水龙头数目 (困难)
 * 在 x 轴上有一个一维的花园。花园长度为n，从点0开始，到点n结束。
 * 花园里总共有n + 1 个水龙头，分别位于[0, 1, ..., n] 。
 * 给你一个整数n和一个长度为n + 1 的整数数组ranges，其中ranges[i] （下标从 0 开始）表示：如果打开点i处的水龙头，可以灌溉的区域为[i - ranges[i], i + ranges[i]]。
 * 请你返回可以灌溉整个花园的最少水龙头数目。如果花园始终存在无法灌溉到的地方，请你返回-1。
 */
public class LeetCode1326 {

    public static void main(String[] arg0) {
        int n = 5;
        int[] ranges = new int[]{3, 4, 1, 1, 0, 0};
        System.out.println("灌溉整个花园的最少水龙头数目 = " + minTaps(n, ranges));
    }

    /**
     * 动态规划，肯定要循环得到每个水龙头的覆盖范围[start_i, end_i]
     * 要取出最少的几个区间覆盖[0, n]，怎么做(动态转移)
     * 记录[0, 1], [0, 2], [0, 3]的最小覆盖水龙头数，假设4的范围是n，那么[0, 4]的最小数量就是 1 + [0, 4-n]
     */
    public static int minTaps(int n, int[] ranges) {
        int[][] intervals = new int[n + 1][];
        for (int i = 0; i <= n; i++) {
            int start = Math.max(i - ranges[i], 0);
            int end = Math.min(i + ranges[i], n);
            intervals[i] = new int[]{start, end};
        }

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] ints, int[] t1) {
                return ints[0] - t1[0]; // 把所有水龙头覆盖范围按起始位置从小到大排序
            }
        });

        int dp[] = new int[n + 1]; // dp[i]代表覆盖[0, i]的最少水龙头数量
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int[] interval : intervals) {
            System.out.println(Arrays.toString(interval));
            int start = interval[0];
            int end = interval[1];

            // 排过序之后第一个 start 不等于 0 直接返回-1
            // 并且后续也发生类似的断层，也返回-1
            if (dp[start] == Integer.MAX_VALUE) {
                return -1;
            }

            for (int i = start; i <= end; i++) {
                dp[i] = Math.min(dp[i], dp[start] + 1);
            }
        }

        return dp[n];
    }

}
